Clone graph [Hash table and BFS]

Time: O(N); Space: O(N); medium

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization: Nodes are labeled uniquely.

We use as a separator for each node, and , as a separator for node label and each neighbor of the node.

Constraints:

  • 1 <= Node.val <= 100

  • Node.val is unique for each node.

  • Number of Nodes will not exceed 100.

  • There is no repeated edges and no self-loops in the graph.

  • The Graph is connected and all nodes can be visited starting from the given node.

Example 1:

Consider the serialized graph {0, 1, 2#1, 2#2, 2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2. Second node is labeled as 1. Connect node 1 to node 2. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle. Visually, the graph looks like the following:

   1
  / \
 /   \
0 --- 2
     / \
     \_/

Example 2:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]

Output: [[2,4],[1,3],[2,4],[1,3]]

Explanation:

  • There are 4 nodes in the graph.

  • 1st node (val = 1)’s neighbors are 2nd node (val = 2) and 4th node (val = 4).

  • 2nd node (val = 2)’s neighbors are 1st node (val = 1) and 3rd node (val = 3).

  • 3rd node (val = 3)’s neighbors are 2nd node (val = 2) and 4th node (val = 4).

  • 4th node (val = 4)’s neighbors are 1st node (val = 1) and 3rd node (val = 3).

[1]:

class UndirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []

[2]:

from collections import deque

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: UndirectedGraphNode
        :rtype: UndirectedGraphNode
        """
        if node == None:
            return None

        que = deque()
        que.append(node)

        visited = set()
        visited.add(node)

        nodes = {}
        idx = 0
        while idx != len(que):
            curr = que[idx]
            idx += 1
            nodes[curr] = UndirectedGraphNode(curr.label)
            for node in curr.neighbors:
                if node not in visited:
                    visited.add(node)
                    que.append(node)

        start_node = None

        for node in que:
            curr = nodes[node]
            for neighbor in node.neighbors:
                curr.neighbors.append(nodes[neighbor])
            if start_node == None:
                start_node = curr

        return start_node

[3]:

if __name__ == "__main__":
    s = Solution()
    node1 = UndirectedGraphNode('1')
    node2 = UndirectedGraphNode('2')
    node3 = UndirectedGraphNode('3')
    node4 = UndirectedGraphNode('4')
    node1.neighbors = [node2, node4]
    node2.neighbors = [node1, node3]
    node3.neighbors = [node2, node4]
    node4.neighbors = [node1, node3]

    cloned_graph = s.cloneGraph(node1)

    print(cloned_graph.label, end = '')
    print(' -> ' + cloned_graph.neighbors[0].label)
    print('  -> ' + cloned_graph.neighbors[1].label)

    print(cloned_graph.neighbors[0].label, end = '')
    print(' -> ' + cloned_graph.neighbors[0].neighbors[0].label)
    print('  -> ' + cloned_graph.neighbors[0].neighbors[1].label)

    print(cloned_graph.neighbors[1].label, end = '')
    print(' -> ' + cloned_graph.neighbors[1].neighbors[0].label)
    print('  -> ' + cloned_graph.neighbors[1].neighbors[1].label)

    print(cloned_graph.neighbors[0].neighbors[1].label, end = '')
    print(' -> ' + cloned_graph.neighbors[0].neighbors[1].neighbors[0].label)
    print('  -> ' + cloned_graph.neighbors[0].neighbors[1].neighbors[1].label)

1 -> 2
  -> 4
2 -> 1
  -> 3
4 -> 1
  -> 3
3 -> 2
  -> 4